import java.util.ArrayList;
import java.util.Iterator;
import java.util.Properties;
import java.util.StringTokenizer;
import java.io.FileInputStream;
import java.io.File;
import java.io.IOException;

/**
 * The main class of the crib program, to attack a ciphertext which has
 * been encrypted using a basic mono-alphabetic substitution cipher, 
 * with word gaps.
 * 
 * @author Tom Castle
 * @version v.1.41 05/11/04
 */
public class Crack    
{
    private CipherText cipherText;
    private Dictionary dict,fullDict;
    private char[] fc,fd,fc_new,fd_new;
    private int dMax,bestScore,scoreEstimate,wordsInStart; 
    private ArrayList cipherWords,allPatternSets,bestPerms,bestPermsFc;
    private String[] cipherWordsA;
    private boolean useEstimate,selfMapping;
    private double dictProportion;
    private String settingsFile;
    private Crib ui;
 
    /**
     * Constructor for objects of class Crack
     */
    public Crack()
    {     
        settingsFile = Crib.SETTINGSFILE;
        //load fullDict early to improve runtime.
        fullDict = new Dictionary(new File("Dictionaries/EnglishLong.txt"));
        init();
    }

    /**
     * Initialise all variables.
     * In seperate method to reduce duplication in clean().
     */
    private void init()
    {
        loadSettings();
        cipherText = new CipherText("");
        fc = new char[26];//encryption
        fd = new char[26];//decryption
        fc_new = new char[26];
        fd_new = new char[26];
        bestScore = 0;
        bestPerms = new ArrayList();
        bestPermsFc = new ArrayList();
        //initialise permutation keys.
        for (int i=0; i<26; i++){
            fc[i] = '*';
            fd[i] = '*';
        }
    }
    
    /**
     * Load the initial settings from the ini file.
     */
    private void loadSettings()
    {
        try{
            Properties p = new Properties();
            p.load(new FileInputStream(new File(settingsFile)));
            dict = new Dictionary(p.getProperty("Dictionary","English.txt"));
            dictProportion = (new Double(p.getProperty("ScoreEstimateProportion","0.45"))).doubleValue();
            useEstimate = (p.getProperty("ScoreEstimation","False").equals("True"));
            selfMapping = (p.getProperty("SelfMappingValid","True").equals("True"));
            wordsInStart = (new Integer(p.getProperty("WordsInStart","40"))).intValue();
        }catch(IOException e){
            //error - try and continue with default settings.
        }

    }

    /**
     * Cleans the crack object of all it's variables apart from
     * the dictionary objects which will be the same and very CPU
     * intensive to reload.
     */
    public void clean()
    {
        init();
    }
    
    /**
     * Returns whether score estimation is in use or not.
     */
    public boolean usingScoreEstimation()
    {
        return useEstimate;
    }

    /**
     * Set the ciphertext variable.
     */
    public void setCipherText(String newCipherText)
    {
        cipherText.setCipherText(newCipherText);
        //get cipher words.
        ArrayList plainCipherWords = cipherText.findStartCipherWords(wordsInStart);
        //get pattern sets.
        allPatternSets = getPatternSets(plainCipherWords);
        //order cipher words, moving pattern sets accordingly.
        //cipherWords = orderCipherWords(plainCipherWords);
        cipherWords = orderCipherWords(plainCipherWords,allPatternSets);
    }

    /**
     * Get the ciphertext object.
     */
    public CipherText getCipherText()
    {
        return cipherText;
    }
    
    /**
     * Set the dictionary to be used.
     */
    public void setDictionary(Dictionary newDict)
    {
        dict = newDict;
    }
    
    /**
     * Generates an ArrayList of pattern sets for each cipherword.
     */
    public ArrayList getPatternSets(ArrayList cipherWords)
    {
        ArrayList patternSets = new ArrayList();
        Iterator it = cipherWords.iterator();
        while(it.hasNext()){
            patternSets.add(dict.getPatternSet((String) it.next()));
        }
        
        return patternSets;
    }
    
    /**
     * Calls solve with the correct initial parameters.
     */
    public void solve()
        throws InterruptedException
    {  
        dMax = cipherWords.size(); //maximum depth of search tree.
        solve(0,fc,fd,0);
    }

    /**
     * Traverses search tree recursively, to find best score.
     * 
     * @param   depth of search tree.
     * @param   partial permutation.
     * @param   number of plainwords used so far from the dictionary.
     */
    private void solve(int Depth, char[] fc, char[] fd, int score)
        throws InterruptedException
    {
        if (Thread.interrupted()) {
            throw new InterruptedException();
         }
        int bestPossibleScore = score + dMax - Depth;

        if (bestPossibleScore < bestScore){ //if the best possible score cannot possibly be beaten.
            //do nothing
        }else if(useEstimate && bestPossibleScore < scoreEstimate){  //if score will be less than the estimated minimum correct.
            //do nothing
        }else if(Depth >= dMax){
            compareScore(score);
        }else{
            String cipherWord = (String) cipherWords.get(Depth);    //hold the cipher word while being worked on.
            ArrayList patternSet = (ArrayList) allPatternSets.get(Depth);
            
            Iterator it = patternSet.iterator();
            while (it.hasNext()){
                if (isConsistent(cipherWord,(String) it.next(),fc,fd)) //if letters haven't already been assigned.
                    solve(Depth+1, fc_new, fd_new, score+1);
            }
            solve(Depth+1, fc, fd, score);
        }
    }
    
    /**
     * Compare score to best found yet, if greater or equal, print.
     */
    private void compareScore(int score)
    {
        if (score == bestScore){
            bestPerms.add(fd_new);
            bestPermsFc.add(fc_new);
        }else if (score > bestScore){
            bestScore = score;
            bestPerms.clear();
            bestPermsFc.clear();
            bestPerms.add(fd_new);
            bestPermsFc.add(fc_new);
        }
    }
    
    /**
     * @return  ArrayList containing all results with highest score.
     */
    public ArrayList getBestPerms()
    {
        return bestPerms;
    }
    
    /**
     * Decrypt ciphertext object using given key
     */
    public String decrypt(char[] key)
    {
        return cipherText.decrypt(key);
    }
    
    /**
     * Checks that the letters haven't already been assigned in
     * partial permutation [f].
     * 
     * @param   cipherword.
     * @param   plainword from pattern set.
     * @param   partial permutation.
     */
    private boolean isConsistent(String W, String X, char[] fc, char[] fd)
    {
        fc_new = (char[]) fc.clone();
        fd_new = (char[]) fd.clone();
        
        for (int i=0; i<W.length(); i++){
            
            char xch = X.charAt(i);
            char wch = W.charAt(i);
            
            //check encryption key.
            int arrayPosX = ((int) xch)-65;
            char fc_char = fc_new[arrayPosX];
            if (((fc_char != '*') && (fc_char != wch)) || ((xch == wch) && !selfMapping)) return false;
            
            //check decryption key.
            int arrayPosW = ((int) wch)-65;
            char fd_char = fd_new[arrayPosW];
            if ((fd_char != '*') && (fd_char != xch)) return false;
            
            fc_new[arrayPosX] = (char) (arrayPosW + 65);
            fd_new[arrayPosW] = (char) (arrayPosX + 65);
        }
        
        return true;
    }
    
    /**
     * Find an estimate for the score of the correct plaintext solution.
     * 
     * @return An int score estimate.
     */
    public int findScoreEstimate()
    {
        int numWords = cipherWords.size();
        //presumption - using dictionary of 135 most frequent. (should get dictionary size first)
        //      -- more words in dictionary means higher proportion likely to be found. 
        scoreEstimate = (int)(numWords * dictProportion);
        return scoreEstimate; //estimate - % of words in dictionary (min).
    }

    /**
     * @return Returns the bestScore.
     */
    public int getBestScore() {
        return bestScore;
    }
    
    /**
     * @return Returns the index of coincidence calculated
     * within ciphertext.
     */
    public double getIOC()
    {
        return cipherText.getIOC();
    }
    
    /**
     * @return Returns the probable language calculated
     * within ciphertext.
     */
    public String getLanguage()
    {
        return cipherText.getLanguage();
    }
    
//***************************************
//***************FILL GAPS***************
//***************************************
//Fill gaps by trying each letter in each position
//  looking for which enhances the score most.

    /**
     * Fill in the gaps in the set of best perms.
     * 
     * GO THROUGH A SECOND TIME (OR x TIMES), RETAINING ALL OTHER ASSIGNED CHARACTERS
     * SEEING IF ONE CAN BE SHIFTED TO MAKE AN IMPROVEMENT.
     */
    public void fillGaps()
    {
        int noPerms = bestPerms.size();
        //for each set of perms
        int n = 0;
        while(n<noPerms){
            //get encryption and decryption keys
            char[] fc_current = (char[]) bestPermsFc.get(n);
            char[] fd_current = (char[]) bestPerms.get(n);
            //get list of unassigned characters.
            int[] fc_gaps = starPos(fc_current);
            int[] fd_gaps = starPos(fd_current);
            //calculate prog sector (must be now, as all values available).
            int noGaps = fc_gaps.length;
            int progressSectorB = (100/noPerms);
            int progressSectorS = progressSectorB/(noGaps*noGaps);
            boolean changed = true;
            while(changed){//do until (all gaps filled or) no new additions are made
                changed = false;
                //for each character of fc_gaps.
                for(int i=0;i<noGaps;i++){
                    //if(fc_gaps[i]==-1) break;//if been assigned in earlier loops.
                    //get the score at the moment.
                    int bestScore = getScore(fd_current,fullDict);
                    int bestScorePos = -1;
                    //assign the character in each position available position in fd_current, specified in fd_gaps.
                    for(int j=0;j<noGaps;j++){
                        if (fd_gaps[j]!=-1){//if not been assigned in earlier loops.
                            fd_current[fd_gaps[j]] = (char)(fc_gaps[i]+65);
                            //find the score for this perm.
                            int currentScore = getScore(fd_current,fullDict);
                            //if greater than best score so far for this character, then save
                            if(currentScore>bestScore){
                                bestScore = currentScore;
                                bestScorePos = j;
                            }
                            //return to star.
                            fd_current[fd_gaps[j]] = '*';
                        }
                    }
                    //insert char in position best scored.
                    if(bestScorePos!=-1){
                        fd_current[fd_gaps[bestScorePos]] = (char)(fc_gaps[i]+65);
                        //remove char from gaps.
                        fd_gaps[bestScorePos] = -1;
                        //fc_gaps[i] = -1;
                        //changed = true;
                    }
                }
                bestPerms.set(n,fd_current);
                bestPermsFc.set(n,fc_current); //FC NEEDS UPDATING TOO
            }
            n++;
        }
    }
    
    /**
     * Take an array of length 26 and return an array of those char 
     * positions with stars.
     */
    private int[] starPos(char[] a)
    {
        //count how many stars.
        int count = 0;
        for(int i=0;i<26;i++){
            if (a[i] == '*')
                count++;
        }
        //create new array.
        int[] starred = new int[count];
        //fill array.
        int j=0;
        for(int i=0;i<26;i++){
            if (a[i] == '*'){
                starred[j] = i;
                j++;
            }
        }
        return starred;
    }    
    
    /**
     * get the score of this permutation, using a full english dictionary.
     */
    private int getScore(char[] perm, Dictionary fullDict)
    {
        
        String posText = cipherText.decrypt(perm);
        int score = 0;
        //for each word, see if it is in dictionary.
        StringTokenizer st = new StringTokenizer(posText);
        while(st.hasMoreTokens()){
            if(fullDict.containsWord(st.nextToken())){
                score++;
            }
        }
        return score;
    }
    
//***************************************
//***********ORDERING HEURISTIC**********
//***************************************
        
    /**
     * Orders the cipherwords by how large their pattern set is, from small to large.
     */
    private ArrayList orderCipherWords(ArrayList cipherWords, ArrayList patternSets)
    {
        int noCipherWords = patternSets.size();
        int[] patternSetCount = new int[noCipherWords];
        //count pattern sets.
        Iterator it = patternSets.iterator();
        int i = 0;
        while(it.hasNext()){
            patternSetCount[i] = ((ArrayList) it.next()).size();
            i++;
        }
        //sort elements
        quickSortPatternSets(patternSetCount,cipherWords,patternSets,0,noCipherWords-1);
        
        return cipherWords;
    }
      
    /**
     * Quicksort elements first to last of array a.
     */
    private void quickSortPatternSets(int a[], ArrayList cipherWords, ArrayList patternSets, int first, int last) {
        int i = first;
        int j = last;
        int pivot = a[(i + j) / 2];
        while (i <= j) {
            while (a[i] < pivot)
                i++;
            while (a[j] > pivot)
                j--;
            if (i <= j) {
                //perform swaps.
                int aTemp = a[i];
                String bTemp = (String) cipherWords.get(i);
                ArrayList cTemp = (ArrayList) patternSets.get(i);
                a[i] = a[j];
                cipherWords.set(i,(String) cipherWords.get(j));
                patternSets.set(i,(ArrayList) patternSets.get(j));
                a[j] = aTemp;
                cipherWords.set(j,bTemp);
                patternSets.set(j,cTemp);
                i++;
                j--;
            }
        }
        if (j > first)
            quickSortPatternSets(a,cipherWords,patternSets,first,j);
        if (i < last)
            quickSortPatternSets(a,cipherWords,patternSets,i,last);
    }
}
